package breadbox.pastry.routing;

import java.util.concurrent.locks.ReadWriteLock;
import java.util.concurrent.locks.ReentrantReadWriteLock;
import java.io.Serializable;
import java.net.InetAddress;

import breadbox.pastry.ID;
import breadbox.pastry.Conf;

public class LeafSet implements Serializable {
	private static final long serialVersionUID = 3873222459657624848L;
	private LeafBinaryTree lower_, higher_;
	private RoutingNode base_;
	private RoutingNode min_, max_;
	private ReadWriteLock lock_;
	
	public LeafSet( LeafSet other ) {
		lower_ = new LeafBinaryTree( );
		higher_ = new LeafBinaryTree( );
		lock_ = new ReentrantReadWriteLock();
		
		if( other != null ) {
			base_ = other.baseNode( );
			RoutingNode[ ] nodes = other.toArray();
			
			if( nodes != null ) {
				for( RoutingNode node : nodes ) {
					insert( node );
				}
			}
		}
	}
	
	private RoutingNode baseNode( ) {
		lock_.readLock().lock();
		RoutingNode ret = new RoutingNode( base_ );
		lock_.readLock().unlock();
		
		return ret;
	}
	
	public LeafSet( RoutingNode base ) {
		base_ = base;
		base_.setType( RoutingNode.RoutingNodeType.LEAF );
		lower_ = new LeafBinaryTree( );
		higher_ = new LeafBinaryTree( );
		lock_ = new ReentrantReadWriteLock( );
		min_ = base_;
		max_ = base_;
	}
	
	public void setBaseIp( InetAddress ip ) {
		lock_.writeLock().lock();
		base_.setIp( ip );
		lock_.writeLock().unlock();
	}
	
	public boolean spans( RoutingNode n ) {
		lock_.readLock().lock();
		
		boolean ret = min( ) != null && max( ) != null 
			&& min( ).compareTo( n ) <= 0 && max( ).compareTo( n ) >= 0;
		
		lock_.readLock().unlock();
		return ret;
	}
	
	public RoutingNode max( ) {
		lock_.readLock().lock();
		RoutingNode max = new RoutingNode( max_ );
		lock_.readLock().unlock();
		
		return max;
	}
	
	public RoutingNode min( ) {
		lock_.readLock().lock();
		RoutingNode min = new RoutingNode( min_ );
		lock_.readLock().unlock();
		
		return min;
	}
	
	public RoutingNode closestNotBase( RoutingNode n ) {
		if( n == null )
			return null;
		RoutingNode[ ] nodes = toArray();
		lock_.readLock().lock();
		RoutingNode ret = null;
		if( nodes != null && nodes.length > 0 ) {
			long dist = Long.MAX_VALUE;
			
			// TODO change this to be a binary search based on toString
			for( RoutingNode node : nodes ) {
				if( node.equals( base_ ) )
					continue;
				
				if( node.getId() != null && node.getId().distance(n.getId()) < dist ) {
					ret = node;
					dist = node.getId().distance(n.getId());
				}
			}
		}
		
		lock_.readLock().unlock();
		
		return ret;
	}
	
	public RoutingNode closest( RoutingNode n ) {
		if( n == null )
			return null;
		RoutingNode[ ] nodes = toArray();
		lock_.readLock().lock();
		RoutingNode ret = null;
		if( nodes != null && nodes.length > 0 ) {
			long dist = Long.MAX_VALUE;
			
			// TODO change this to be a binary search based on toString
			for( RoutingNode node : nodes ) {
				if( node.getId() != null && node.getId().distance(n.getId()) < dist ) {
					ret = node;
					dist = node.getId().distance(n.getId());
				}
			}
		}
		
//		if( n.compareTo( base_ ) < 0 && lower_.size( ) > 0 ) {
//			ret = new RoutingNode( lower_.closest( n ) );
//			
//			if( ret.getId().distance(n.getId()) > base_.getId().distance(n.getId())) {
//				ret = new RoutingNode( base_ );
//			}
//		} else if( n.compareTo( base_ ) > 0 && higher_.size( ) > 0 ) {
//			ret = new RoutingNode( higher_.closest( n ) );
//			
//			if( ret.getId().distance(n.getId()) > base_.getId().distance(n.getId())) {
//				ret = new RoutingNode( base_ );
//			}
//		} else {
//			ret = new RoutingNode( base_ );
//		}
		lock_.readLock().unlock();
		
		return ret;
	}
	
	/**
	 * Returns the given number of IDs closest to the given ID
	 * @param target
	 * @param number
	 * @return
	 */
	public ID[ ] closest( ID target, int number ) {
		lock_.readLock().lock();
		
		RoutingNode[ ] nodes = toArray( );
		
		if( nodes == null ) {
			lock_.readLock().unlock();
			return null;
		}
		
		int size = Math.min( number, nodes.length );
		ID[ ] ids = new ID[ size ];
		RoutingNode rn = new RoutingNode( target );
		
		RoutingNode closest = closest( rn );
		
		int target_i = -1;
		for( int i = 0; i < nodes.length; i++ ) {
			if( nodes[ i ].equals( closest ) ) {
				target_i = i;
				break;
			}
		}
		
		int start = Math.max( 0, target_i - number / 2 );
		int j = 0;
		for( int i = start; i < nodes.length && i < start + number; i++ ) {
			ids[ j ] = nodes[ i ].getId();
		}
		
		lock_.readLock().unlock();
		return ids;
	}
	
	public void insert( RoutingNode n ) {
		if( n == null )
			return;
		
		lock_.writeLock().lock();
		if( ( lower_.size( ) >= Conf.l() / 2 && n.compareTo( lower_.min( ) ) < 0 ) ||
			( higher_.size( ) >= Conf.l() / 2 && n.compareTo( higher_.max( ) ) > 0 ) ) {
			lock_.writeLock().unlock();
			return;
		}
		
		n.setType( RoutingNode.RoutingNodeType.LEAF );
		if( n.compareTo( base_ ) < 0 ) {
			lower_.insert( n );
			
			if( lower_.size( ) > Conf.l( ) / 2 ) {
				lower_.remove( lower_.min( ) );
			}
		} else if( n.compareTo( base_ ) > 0 ) {
			higher_.insert( n );
			
			if( higher_.size( ) > Conf.l( ) / 2 ) {
				higher_.remove( higher_.max( ) );
			}
		}
		
		updateExtrema( );
		lock_.writeLock().unlock();
	}
	
	private void updateExtrema( ) {
		// update extrema
		if( lower_ != null && !lower_.isEmpty( ) ) {
			min_ = lower_.min( );
		} else if( base_ != null ) {
			min_ = base_;
		}
		
		if( higher_ != null && !higher_.isEmpty( ) ) {
			max_ = higher_.max( );
		} else if( base_ != null ) {
			max_ = base_;
		}
	}
	
	public RoutingNode remove( RoutingNode n ) {
		if( n == null )
			return null;
		
		lock_.writeLock().lock();
		RoutingNode ret = null;
		if( n.compareTo( base_ ) < 0 ) {
			ret = lower_.remove( n );
		} else if( n.compareTo( base_ ) > 0 ) {
			ret = higher_.remove( n );
		}
		
		updateExtrema( );
		lock_.writeLock().unlock();
		
		return ret;
	}
	
	public RoutingNode[ ] toArray( ) {
		lock_.readLock().lock();
		RoutingNode[ ] r = new RoutingNode[ lower_.size() + higher_.size() + 1 ];
		
		RoutingNode[ ] l = lower_.toArray( );
		RoutingNode[ ] h = higher_.toArray( );
		
		int i = 0;
		if( l != null ) {
			for( i = 0; i < l.length; i++ ) {
				r[ i ] = new RoutingNode( l[ i ] );
			}
		}
		
		r[ i++ ] = new RoutingNode( base_ );
		
		if( h != null ) {
			for( int j = 0; j < h.length; j++, i++ ) {
				r[ i ] = new RoutingNode( h[ j ] );
			}
		}
		
		lock_.readLock().unlock();
		return r;
	}
}
